#include <iostream>
#include <vector>
#include <algorithm>
#include <windows.h>
using namespace std;

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());
        int k = 0;
        for (; k < nums.size() - 2; k++) {
            if (nums[k] > 0)
                break;
            if (k > 0 && nums[k] == nums[k - 1])
                continue; // 跳过重复值

            int l = k + 1;
            int r = nums.size() - 1;

            while (l<r) {
                int sum=0;
                sum=nums[k]+nums[l]+nums[r];
                if (sum<0)
                    l++;
                else if (sum>0)
                    r--;
                else {
                    ans.emplace_back(vector<int>{nums[k], nums[l], nums[r]});
                    // 去重 l 和 r
                    while (l < r && nums[l] == nums[l + 1])
                        l++;
                    while (l < r && nums[r] == nums[r - 1])
                        r--;

                        l++;
                        r--;

                }
            }
        }
        return ans;
    }
};

void printResult(const vector<vector<int>>& result) {
    cout << "[";
    for (size_t i = 0; i < result.size(); ++i) {
        cout << "[";
        for (size_t j = 0; j < result[i].size(); ++j) {
            cout << result[i][j];
            if (j < result[i].size() - 1) cout << ",";
        }
        cout << "]";
        if (i < result.size() - 1) cout << ",";
    }
    cout << "]" << endl;
}

int main() {
    // 设置控制台输出为UTF-8编码
    SetConsoleOutputCP(CP_UTF8);
    
    Solution s;
    
    // 测试用例1：标准情况
    vector<int> nums1 = {-1, 0, 1, 2, -1, -4};
    cout << "测试用例1 - 标准情况：" << endl;
    cout << "输入：nums = [-1,0,1,2,-1,-4]" << endl;
    cout << "输出：";
    printResult(s.threeSum(nums1));
    cout << "预期：[[-1,-1,2],[-1,0,1]]" << endl << endl;
    
    // 测试用例2：全为零的情况
    vector<int> nums2 = {0, 0, 0, 0};
    cout << "测试用例2 - 全零情况：" << endl;
    cout << "输入：nums = [0,0,0,0]" << endl;
    cout << "输出：";
    printResult(s.threeSum(nums2));
    cout << "预期：[[0,0,0]]" << endl << endl;
    
    // 测试用例3：无解情况
    vector<int> nums3 = {1, 2, 3, 4, 5};
    cout << "测试用例3 - 无解情况：" << endl;
    cout << "输入：nums = [1,2,3,4,5]" << endl;
    cout << "输出：";
    printResult(s.threeSum(nums3));
    cout << "预期：[]" << endl << endl;
    
    // 测试用例4：包含重复元素
    vector<int> nums4 = {-2, 0, 1, 1, 2};
    cout << "测试用例4 - 重复元素：" << endl;
    cout << "输入：nums = [-2,0,1,1,2]" << endl;
    cout << "输出：";
    printResult(s.threeSum(nums4));
    cout << "预期：[[-2,0,2],[-2,1,1]]" << endl;

    return 0;
}
